/*
 * SearchUnit.hpp
 *
 *  Created on: 2013-1-16
 *      Author: heqiu
 */

#ifndef SEARCHUNIT_HPP_
#define SEARCHUNIT_HPP_

#include "mycomm.h"
#include "MapUnit.hpp"

class SearchUnit {
public:
	typedef struct _WayNode {
		uint32_t uiX;
		uint32_t uiY;
		uint32_t uiNo;
	} WayNode;
	static bool findWay(uint32_t from_x, uint32_t from_y, uint32_t to_x,
			uint32_t to_y, MapUnit & map,
			vector<pair<uint32_t, uint32_t> > & vctPath) {
		pair<uint32_t, uint32_t> stPair;
		stPair.first = from_x;
		stPair.second = from_y;
		vctPath.push_back(stPair);
		if (from_x == to_x && from_y == to_y) {
			return true;
		}
		uint32_t uiLen = map.m_uiLong;
		map.clearWayFlag();
		//开始寻路
		uint32_t uiX = from_x;
		uint32_t uiY = from_y;
		bool bFound = false;
		WayNode stWayNode;
		vector<WayNode> vctWayNode;
		int iNo = 0;
		stWayNode.uiNo = 0;
		stWayNode.uiX = uiX;
		stWayNode.uiY = uiY;
		vector<WayNode> vctTmp;
		vctTmp.push_back(stWayNode);
		vctWayNode.push_back(stWayNode);
		uint32_t uiBeginPos = 0;
		uint32_t uiNum = 1;
		while (true) {
			vector<WayNode> vctTmp2;
			for (uint32_t ui = 0; ui < vctTmp.size(); ui++) {
				uiX = vctTmp.at(ui).uiX;
				uiY = vctTmp.at(ui).uiY;
				//四个方向
				//上
				stWayNode.uiNo = uiBeginPos + ui;
				stWayNode.uiX = uiX;
				stWayNode.uiY = uiY - 1;
				if (map.isWay(stWayNode.uiX, stWayNode.uiY)
						&& !map.isWayFlag(stWayNode.uiX, stWayNode.uiY)) {
					map.setWayFlag(stWayNode.uiX, stWayNode.uiY);
					vctWayNode.push_back(stWayNode);
					if (stWayNode.uiX == to_x && stWayNode.uiY == to_y) {
						bFound = true;
						goto foundway;
					}
					vctTmp2.push_back(stWayNode);
				}
				//右
				stWayNode.uiNo = uiBeginPos + ui;
				stWayNode.uiX = uiX + 1;
				stWayNode.uiY = uiY;
				if (map.isWay(stWayNode.uiX, stWayNode.uiY)
						&& !map.isWayFlag(stWayNode.uiX, stWayNode.uiY)) {
					map.setWayFlag(stWayNode.uiX, stWayNode.uiY);
					vctWayNode.push_back(stWayNode);
					if (stWayNode.uiX == to_x && stWayNode.uiY == to_y) {
						bFound = true;
						goto foundway;
					}
					vctTmp2.push_back(stWayNode);
				}
				//下
				stWayNode.uiNo = uiBeginPos + ui;
				stWayNode.uiX = uiX;
				stWayNode.uiY = uiY + 1;
				if (map.isWay(stWayNode.uiX, stWayNode.uiY)
						&& !map.isWayFlag(stWayNode.uiX, stWayNode.uiY)) {
					map.setWayFlag(stWayNode.uiX, stWayNode.uiY);
					vctWayNode.push_back(stWayNode);
					if (stWayNode.uiX == to_x && stWayNode.uiY == to_y) {
						bFound = true;
						goto foundway;
					}
					vctTmp2.push_back(stWayNode);
				}
				//左
				stWayNode.uiNo = uiBeginPos + ui;
				stWayNode.uiX = uiX - 1;
				stWayNode.uiY = uiY;
				if (map.isWay(stWayNode.uiX, stWayNode.uiY)
						&& !map.isWayFlag(stWayNode.uiX, stWayNode.uiY)) {
					map.setWayFlag(stWayNode.uiX, stWayNode.uiY);
					vctWayNode.push_back(stWayNode);
					if (stWayNode.uiX == to_x && stWayNode.uiY == to_y) {
						bFound = true;
						goto foundway;
					}
					vctTmp2.push_back(stWayNode);
				}
			}
			uiNum++;
			uiBeginPos += vctTmp.size();
			vctTmp.swap(vctTmp2);
			if (vctTmp.size() == 0) {
				//无路可走
				break;
			}
		}
		foundway: if (bFound) {
			/*
			 for (int i = 0; i < vctWayNode.size(); i++) {
			 printf("i:%d  x=%d y=%d pos=%d\n", i, vctWayNode.at(i).uiX,
			 vctWayNode.at(i).uiY, vctWayNode.at(i).uiNo);
			 }
			 */

			vctPath.resize(uiNum + 1);
			uint32_t uiTmpPos = vctWayNode.size() - 1;
			printf("uiNum=%d\n", uiNum);
			for (uint32_t ui = uiNum; ui > 0; ui--) {
				vctPath.at(ui).first = vctWayNode.at(uiTmpPos).uiX;
				vctPath.at(ui).second = vctWayNode.at(uiTmpPos).uiY;
				uiTmpPos = vctWayNode.at(uiTmpPos).uiNo;
				//	printf("x=%d y=%d uiTmpPos=%d uiNo=%d\n", vctPath.at(ui).first,vctPath.at(ui).second, uiTmpPos,vctWayNode.at(uiTmpPos).uiNo);
			}
			/*
			 printf("path.size=%d\n", vctPath.size());
			 for (int i = 0; i < vctPath.size(); i++) {
			 printf("i:%d x=%d y=%d\n", i, vctPath.at(i).first,
			 vctPath.at(i).second);
			 }
			 */
		}
		return bFound;
	}
};

#endif /* SEARCHUNIT_HPP_ */
